import java.util.Random;

/**
 * 排序模版，定义所有用到的方法
 */
public abstract class TemplateSort {

    /**
     * 排序算法实现体
     * @param a
     */
    abstract void sort(Comparable[] a);

    /**
     * 创建整数数据
     * @param min 最小值
     * @param max 最大值
     * @param count 数组长度
     * @return
     */
    public Comparable[] createInt(int min, int max, int count) {
        Comparable[] a = new Integer[count];
        Random random = new Random();

        for (int i = 0; i < count; i++) {
            a [i] = random.nextInt(max) % (max - min + 1) + min;
        }

        return a;
    }

    /**
     * 比较两元素大小
     * @param v
     * @param w
     * @return
     */
    public boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    /**
     * 互换两元素
     * @param a
     * @param i
     * @param j
     */
    public void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印整个数组
     * @param a
     */
    public void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + "\t\t");
        }
        System.out.println();
    }

    /**
     * 验证整个数组是否有序
     * @param a
     * @return
     */
    public boolean isSorted(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            if (less(a[i], a[i - 1])) {
                return false;
            }
        }
        return true;
    }

    /**
     * 测试方法
     * @param a
     */
    public void run(Comparable[] a) {
        // 排序前
        System.out.println("---- before sort ----");
        show(a);

        // 排序
        long beginTime = System.currentTimeMillis();
        sort(a);
        long endTime = System.currentTimeMillis();
        System.out.println("耗时：" + (endTime - beginTime) + " ms");

        // 验证
        assert isSorted(a);

        // 排序后
        System.out.println("---- after sort ----");
        show(a);
    }

}
